package com.leetcode.algorithm.y22.m08.w2;

import java.util.ArrayList;
import java.util.List;

/**
 * 22. 括号生成
 * 
 * https://leetcode.cn/problems/generate-parentheses/
 * 
 * @author jie.deng
 *
 */
class Question0022Solution01 {

	public List<String> generateParenthesis(int n) {
		List<String> result = new ArrayList<>();
		char[] chArr = new char[n * 2];
		backtracking(result, n, 0, 0, chArr);
		return result;
	}

	private void backtracking(List<String> result, int n, int leftCnt, int rightCnt, char[] chArr) {
		if (leftCnt == n && rightCnt == n) {
			result.add(String.valueOf(chArr));
			return;
		}
		if (rightCnt > leftCnt || leftCnt > n) {
			return;
		}
		chArr[leftCnt + rightCnt] = '(';
		backtracking(result, n, leftCnt + 1, rightCnt, chArr);

		chArr[leftCnt + rightCnt] = ')';
		backtracking(result, n, leftCnt, rightCnt + 1, chArr);
	}

}